//按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 
//
// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 
//
// 
// 
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
// 
// 
//
// 
//
// 示例 1： 
// 
// 
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[["Q"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 
//
// Related Topics 数组 回溯 👍 1888 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2023-09-07 21:57:04
 * @description 51.N 皇后
 */
public class NQueens{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new NQueens().new Solution();
		 System.out.println(solution.solveNQueens(4));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 int dep,count;
		 List <List<String>> res;
		 List<String> ans;
		 boolean[] clo;
		 boolean[] l;
		 boolean[] r;
		 char[][]g;
    public List<List<String>> solveNQueens(int n) {
		dep=n;
		count=n;
		clo=new boolean[n];
		l=new boolean[2*n-1];
		r=new boolean[2*n-1];
		res=new ArrayList<>();
		ans=new ArrayList<>();
		g=new char[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				g[i][j]='.';
			}
		}
		dfs(0);
		return res;
    }
	private void dfs(int curr){
		if(curr==dep){
			res.add(new ArrayList<>(ans));
			return;
		}
		for (int i = 0; i < dep; i++) {
			if(!clo[i]&&!l[i+curr]&&!r[dep-i+curr-1]){
				clo[i]=true;
				l[i+curr]=true;
				r[dep-i+curr-1]=true;
				g[curr][i]='Q';
				ans.add(new String(g[curr]));
				dfs(curr+1);
				ans.remove(ans.size()-1);
				g[curr][i]='.';
				clo[i]=false;
				l[i+curr]=false;
				r[dep-i+curr-1]=false;
			}
		}
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
